//#include<iostream>
//using namespace std;
//int sum(int a[], int i, int j) {
//	int sum = 0;
//	for (int m = i; m <= j; m++)
//		sum += a[m];
//	return sum;
//}
//void minPower(int n, int a[], int f[][201]) {
//	int len, i, j, k;
//	for (len = 2; len <= n; len++)
//		for (i = 1; i <= n; i++) {
//			j = i + len - 1;
//			if (j > n)
//				continue;
//			f[i][j] = 10000000;
//			for (k = i; k <= j - 1; k++)
//				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum(a, i, j));
//		}
//}
//int main() {
//	int n, a[201]{ 0 }, b[201]{ 0 }, c[201]{ 0 };
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		if (i != 1) {
//			b[i] = a[i - 1];
//			c[i-1] = a[i];
//		}
//	}
//	b[1] = a[n];
//	c[n] = a[1];
//	int f[201][201]{ 0 }, g[201][201]{ 0 }, h[201][201]{ 0 };
//	int len, i, j, k;
//	minPower(n, b, g);
//	minPower(n, c, h);
//	minPower(n, a, f);
//	//for (len = 2; len <= n; len++)
//	//	for (i = 1; i <= n; i++) {
//	//		j = i + len - 1;
//	//		if (j > n)
//	//			continue;
//	//		f[i][j] = 10000000;
//	//		for (k = i; k <= j - 1; k++) {
//	//			f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum(a, i, j));
//	// 			//cout << "f["<<i<<"]["<<j<<"]=" << f[i][j] << endl;
//	//			//if (i == 1 && j == n) {
//	//			//	f[i][j] = min(f[i][j], g[i][k + 1] + g[k + 2][j] + sum(b, i, j));
//	//			//	f[i][j] = min(f[i][j], h[i][k - 1] + h[k][j] + sum(c, i, j));
//	//			//}
//	//		}
//	//	}
//	f[1][n] = min(f[1][n], g[1][n]);
//	f[1][n] = min(f[1][n], h[1][n]);
//	cout << f[1][n] << endl;
//	return 0;
//}